package org.example.sort;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/3/14 9:50
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {3,30,34,5,9};
        MergeSort mergeSort = new MergeSort();
        int[] temp = new int[nums.length];
        mergeSort.mergeSortFun(nums,0,nums.length - 1,temp);
        for (int i : nums){
            System.out.println(i);
        }
    }


    //入口函数
    public void mergeSortFun(int[] nums,int start,int end,int[] temp){
        if(start >= end){
            return;
        }
        int m = (start + end) / 2;
        mergeSortFun(nums,0,m,temp);
        mergeSortFun(nums, m+1, end, temp);

        merge(nums,start,m,end,temp);
    }


    public void merge(int[] nums,int left,int mid,int right,int[] temp){
       int i = left;
       int j = mid  + 1;
       int t = 0;
       while (i <= mid && j <= right){
           if(nums[i] <= nums[j]){
               temp[t++] = nums[i++];
           }else{
               temp[t++] = nums[j++];
           }
       }
       if(i <= mid){
           temp[t++] = nums[i++];
       }
       if(j <= right){
           temp[t++] = nums[j++];
       }
       t = 0;
       while (left <= right){
           nums[left++] = temp[t++];
       }
    }

    /**
     归并排序
     */
    public void mergeSort(int[] nums,int left,int right){
        //递归的终止条件
        if(left >= right){
            return;
        }

        //递归划分
        int m = (left + right) / 2;
        mergeSort(nums, 0, m);
        mergeSort(nums, m + 1, right);
        //合并子数组
        int[] tmp = new int[right - left + 1];
        for(int i = left; i <= right; i++){
            tmp[i - left] = nums[i];
        }
        //左右数组的首个元素指针
        int i = 0,j = m - left + 1;
        for(int k = left; k <= right; k++){
            if(i == m - left + 1){
                nums[k] = tmp[j++];
            }else if(j == right - left + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
            }
        }

    }

}
